package stack;

import java.util.Stack;

//有效括号问题
public class StackProblem {
    public boolean isValid(String s){
        //先创建一个栈
        Stack<Character> stack = new Stack<>();//char的包装类是Character
        //针对字符串进行遍历,取出每个字符
        for(int i = 0;i < s.length();i++){
            char c = s.charAt(i);
            //包装类虽然是引用类型,但是可以自动拆箱,因此可以用"=="来判定相等
            if(c == '[' || c == '(' || c == '{'){
                stack.push(c);
                continue;
            }
            if(c == ']' || c == ')' || c == '}'){
                if(stack.isEmpty()){
                    return false;
                }
                char top = stack.pop();
                if(top == '(' && c == ')'){
                    continue;
                }
                if(top == '[' && c == ']'){
                    continue;
                }
                if(top == '{' && c == '}'){
                    continue;
                }
                return false;
            }
        }
        if(stack.isEmpty()){
            return false;
        }
        return true;
    }




    //逆波兰表达式计算结果的
    public int evalRPN(String [] tokens){
        //先准备一个栈,用来放操作数
        Stack<Integer> stack = new Stack<>();
        for(String token : tokens){
            if(isNumber(token)){
                //入栈时把字符类型转为整数类型,并进行入栈操作
                stack.push(Integer.parseInt(token));
                continue;
                //注意这个continue的作用,不遇到运算符的话,是不会执行下面的代码的
            }
            int num2 = stack.pop();
            int num1 = stack.pop();
            if(token.equals("+")){
                stack.push(num1 + num2);
            }else if(token.equals("-")){
                stack.push(num2 - num1);
            }else if(token.equals("*")){
                stack.push(num1 * num2);
            }else if(token.equals("/")){
                stack.push(num2 / num1);
            }
        }
        //比如1 2 -   这时候表示的是1-2,2先出栈,1后出栈,后出栈的放前面,先出栈的放后面
        return stack.pop();
    }

    public static boolean isNumber(String token){
        if(token.equals("+")||token.equals("-")||token.equals("*")||token.equals("/")){
            return false;
        }
        return true;
    }


    //给出入栈顺序,判断给出的出栈顺序是否能够实现,

    //给的都是数组,采用这样的策略,先进行入栈(),
    // 对第一个数组进行遍历,每入一次栈,都判断出栈数组的第一个元素和栈顶元素是否相等,
    //如果相等,栈顶元素出栈,接着继续判断下一个栈顶元素,如果栈为空了,继续入栈,再进行下一轮判断,
    //最后如果PushA的遍历次数用完了,栈还不为空,说明出栈顺序实现不了,否则就是可以

    public static boolean isPopOrder(int [] pushA,int [] popA){
        //1.准备一个栈
        Stack<Integer> stack = new Stack<>();
        int PushIndex = 0;
        int PopIndex = 0;
        for(;PushIndex < pushA.length;PushIndex++){
            stack.push(pushA[PushIndex]);
            //进行栈顶元素匹配
            while(!stack.isEmpty()&&stack.peek() == popA[PopIndex]){
                stack.pop();
                PopIndex++;
            }
            //如果不匹配或者栈为空,直接进入到下次循环即可
        }
        if(stack.isEmpty()){
            return true;
        }
        return false;
    }
}


